#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:

    int getCoins(vector<int>& coins) {
        int n = coins.size();
        vector<int> arr(n + 2, 0);
        arr[0] = 1;
        arr[n + 1] = 1;
        for (int i = 1; i <= n; i++)arr[i] = coins[i - 1];
        vector<vector<int>> dp(n + 2, vector<int>(n + 2));

        for (int i = n; i >= 1; i--) {
            for (int j = 1; j <= n; j++) {
                for (int k = i; k <= j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[k] * arr[i - 1] * arr[j + 1]);
                }
            }
        }
        return dp[1][n];
    }
};